#define _CRT_SECURE_NO_WARNINGS
typedef char BTDataType;
typedef struct TreeNode
{
	BTDataType data;
	struct TreeNode* left;
	struct TreeNode* right;
}TreeNode;
#include"队列.h"
void Leveloreder(TreeNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q,root);
	}
	while (!QueueEmpty(&q))
	{
		TreeNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", front->data);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	QueueDestroy(&q);
}

TreeNode* CreatTree(char* str, int* pi)
{
	if (str[*pi] == '#')
	{
		++(*pi);
		return NULL;
	}
	TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
	root->data = str[*(pi)];
	(*pi)++;
	root->left = CreatTree(str, pi);
	root->right = CreatTree(str, pi);
	return root;
}

void PrevOrder(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%c ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

void  InOrder(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

void PostOrder(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}
int TreeLeafSize(TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
int main()
{
	//TreeNode n1;
	//TreeNode n2;
	//TreeNode n3;
	//TreeNode n4;
	//TreeNode n5;
	//n1.left = &n2;
	//n1.right = &n3;
	//n3.left = NULL;
	//n3.right = NULL;
	//n2.right = NULL;
	//n2.left = &n4;
	//n2.right = &n5;
	//n4.left = NULL;
	//n4.right = NULL;
	//n5.left = NULL;
	//n5.right = NULL;
	//n1.data = 'A';
	//n2.data = 'B';
	//n3.data = 'C';
	//n4.data = 'D';
	//n5.data = 'E';
	char str[100];
	scanf("%s", str);
	int i = 0;
	TreeNode* root=CreatTree(str, &i);
	printf("Leveloreder:");
	Leveloreder(root);
	printf("\n");
	printf("PrevOrder:");
	PrevOrder(root);
	printf("\n");
	printf("InOrder:");
	InOrder(root);
	printf("\n");
	printf("PostOrder:");
	PostOrder(root);
	printf("\n");
	printf("TreeLeafSize:");
	printf("%d", TreeLeafSize(root));
	return 0;
}